
/**
 * 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
 * 
 */

var rob = function(root) {
  if (!root) return 0;
  if (root.left === null && root.right === null) return root.val;

  const memo = new Map();

  function helper(node) {
    if (!node) return 0;
    if (!node.left &&!node.right) return node.val;
    if (memo.has(node)) return memo.get(node);

    // 选择偷当前节点--不选择偷左右子节点
    let val1 = node.val;
    if (node.left) val1 += helper(node.left.left) + helper(node.left.right);
    if (node.right) val1 += helper(node.right.left) + helper(node.right.right);

    // 不选择偷当前节点--选择偷左右子节点
    let val2 = helper(node.left) + helper(node.right);

    memo.set(node, Math.max(val1, val2));
    return memo.get(node);
  }

  return helper(root);
};